package T31_T40;
public class T34 {
    public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
    //思路：方法与合并两个链表类似，将k个链表两两合并，直到没有链表为止
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        int k = lists.length;

        // 循环直到所有链表合并成一个
        //k尽管是j++得到的，但是j会逐渐减小直到为1
        while (k > 1) {
            int j = 0; // 合并后的链表位置
            // 两两合并链表
            for (int i = 0; i < k; i += 2) {
                if (i + 1 < k) {
                    lists[j] = mergeLists(lists[i], lists[i + 1]); // 合并第i和i+1的链表
                } else {
                    lists[j] = lists[i]; // 只有一个链表，直接赋值
                }
                j++; // 更新合并后的位置
            }
            k = j; // 更新合并后的链表数量
        }

        return lists[0]; // 返回最终合并后的链表
    }
    //合并两个链表
    public ListNode mergeLists(ListNode list1,ListNode list2){
        //核心思想：递归
        if (list1==null)return list2;
        if (list2==null)return list1;
        ListNode res = new ListNode();
        if (list1.val<list2.val){
            res.val= list1.val;
            res.next=mergeLists(list1.next,list2);
        }else {
            res.val= list2.val;
            res.next=mergeLists(list1,list2.next);
        }
        return res;
    }
}